package myset

type numeric interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}
type DisjointSet[T numeric] struct {
	f  []T
	sz []int
}

func (dsu *DisjointSet[T]) NewDisjointSet(n int) {
	dsu.f = make([]T, 0, n)
	dsu.sz = make([]int, 0, n)
	for i := T(0); i < T(n); i++ {
		dsu.f = append(dsu.f, i)
		dsu.sz = append(dsu.sz, 1)
	}
}

func (dsu *DisjointSet[T]) Find(x T) T {
	for x != dsu.f[x] {
		dsu.f[x] = dsu.f[dsu.f[x]]
		x = dsu.f[x]
	}
	return x
}

func (dsu *DisjointSet[T]) Same(x, y T) bool {
	return dsu.Find(x) == dsu.Find(y)
}

func (dsu *DisjointSet[T]) Merge(x, y T) bool {
	x = dsu.Find(x)
	y = dsu.Find(y)
	if x == y {
		return false
	}
	dsu.sz[x] += dsu.sz[y]
	dsu.f[y] = x
	return true
}

func (dsu *DisjointSet[T]) Size(x T) int {
	return dsu.sz[x]
}

type DisjointSetWithRollBack[T numeric] struct {
	sz      []int
	f       []T
	history [][2]T
}

func (dsu *DisjointSetWithRollBack[T]) NewDisjointSetWithRollback(n int) {
	dsu.f = make([]T, 0, n+1)
	dsu.sz = make([]int, 0, n+1)
	for i := T(0); i < T(n+1); i++ {
		dsu.f = append(dsu.f, i)
		dsu.sz = append(dsu.sz, 1)
	}
}

func (dsu *DisjointSetWithRollBack[T]) Find(x T) T {
	for dsu.f[x] != x {
		x = dsu.f[x]
	}
	return x
}

func (dsu *DisjointSetWithRollBack[T]) Merge(x, y T) bool {
	x = dsu.Find(x)
	y = dsu.Find(y)
	if x == y {
		return false
	}
	if dsu.sz[x] < dsu.sz[y] {
		x, y = y, x
	}
	dsu.history = append(dsu.history, [2]T{x, y})
	dsu.sz[x] += dsu.sz[y]
	dsu.f[y] = x
	return true
}

func (dsu *DisjointSetWithRollBack[T]) Time() int {
	return len(dsu.history)
}

func (dsu *DisjointSetWithRollBack[T]) Revert(tm int) {
	for dsu.Time() > tm {
		back := dsu.history[dsu.Time()-1]
		x, y := back[0], back[1]
		dsu.history = dsu.history[:dsu.Time()-1]
		dsu.f[y] = y
		dsu.sz[x] -= dsu.sz[y]
	}
}
